console.log('hello wangyi')
/* var isPerfectSquare = function(num) {
    // let res = false
    // for(let i = 1; i <= num; i++){
    //     if((num / i) === i){
    //         res = true
    //         break
    //     }
    // }
    // return res

    // 使用牛顿迭代法
    let x0 = num
    while(1){
        let x1
        x1 = Math.floor((x0 * x0 + num) / (2 * x0))
        if(x0 - x1 <= 1e-6) break
        x0 = x1
    }
    return x0
};
let a = isPerfectSquare(16)
console.log(a)
 */
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
/*  var searchInsert = function(nums, target) {
    let low = 0
    let high = nums.length - 1;
    let res = 0
    debugger
    while(low <= high){
        let mid = Math.floor((low + high) / 2)
        let temp = nums[mid]
        if(low === high && nums[mid]!== target){
            //没有这个值,返回它的插入位置
            res = mid + 1
        }
        if(temp > target){
            high = mid - 1
        }else if(temp < target){
            low = mid + 1
        }else{
            res = mid 
            break
        }
    }
};
let nums = [1,3,5,6]
let res = searchInsert(nums,2)
console.log(res) */

/* var moveZeroes = function(nums) {
    debugger
    let slow = 0
    let quick = 0
    while(quick < nums.length){
        if(nums[quick]){
            let  temp = nums[quick]
            nums[quick] = nums[slow]
            nums[slow] = temp
            slow++
        }
        quick++
    }
};
let arr = [0,1,0,3,12]
moveZeroes(arr)
console.log(arr) */

/* var reverseWords = function(s) {
    let res = s.split(" ")
    let resStr = ''
    console.log(res)
    for(let i = 0; i < res.length; i++){
        let strL = res[i].length
        let tempArr = res[i].split('')
        for(let j = 0; j < Math.floor(strL/2); j++){
            let temp = tempArr[j]
            tempArr[j] = tempArr[strL - j - 1]
            tempArr[strL - j - 1] = temp
        }
        resStr = resStr + tempArr.join("") + ' '
        tempArr = null
    }
    return resStr.substring(0,resStr.length - 1)
};
let res = reverseWords('you are my sun shine')
console.log('res:',res) */

/**
 * @param {number[][]} image
 * @param {number} sr
 * @param {number} sc
 * @param {number} newColor
 * @return {number[][]}
 */
 /* var floodFill = function(image, sr, sc, newColor) {
    // 创建一个执行队列保存待遍历的节点
    let Queue = []
    //  创建一个相同的标识数组，标识当前的点是否应该被修改
    let State = []
    let len1 = image.length
    let len2 = image[0].length
    for(let i = 0; i < len1; i++){
        State[i] = new Array(len2).fill(false)
    }
    let start = image[sr][sc]
    debugger
    State[sr][sc] = true
    Queue.push([sr,sc])
    while(Queue.length){
        // 这里是用的局部作用域和外边得到sr,sc不冲突
    let [sr,sc] = Queue.shift()
    image[sr][sc] = newColor
        //四个方向如果值和当前的相等也设置为true 该方向存在且值等于规定值，并且没有被遍历过
    if(sr>=1 && image[sr - 1][sc] === start && State[sr - 1][sc] === false){
        //上方
        State[sr - 1][sc] = true
        Queue.push([sr - 1,sc])

    }
    if(sr<(len1 - 1) && image[sr + 1][sc] === start && State[sr + 1][sc] === false){
        //下方
        State[sr + 1][sc] = true
        Queue.push([sr + 1,sc])
    }
    if(sc >= 1 && image[sr][sc - 1] === start && State[sr][sc -1] === false){
        // 左边
        State[sr][sc -1] = true
        Queue.push([sr,sc - 1])
    }
    if(sc < (len2 - 1) && image[sr][sc - 1] === start && State[sr][sc + 1] === false){
        // 右边边
        State[sr][sc + 1] = true
        Queue.push([sr,sc + 1])
    }
    }
    return image
};
let imgae =[[1,1,1],[1,1,0],[1,0,1]]
let sr = 1
let sc = 1
let newColor = 2
let res = floodFill(imgae,sr,sc,newColor) */


/* var maxAreaOfIsland = function(grid) {
    // 使用一个标识数组来标识当前的节点是否被访问过
    let rol = grid.length
    let col = grid[0].length
    let TAG = []
    for(let i = 0; i < rol; i++){
        TAG[i] = new Array(col).fill(false)
    }
    // 使用一个队列统计当前的岛屿的面积
    let Queue = []
    // 使用一个数组保存遍历过所有岛屿的面积 ->优化只需用一个遍历保存最大的即可
    let res = 0
    //思路：二重循环遍历当前的点，如果遇到陆地，就将他放入到队列中标识置为true，如果队列不为空就 将队列中的第一个出队列并且将它的四个方向的陆地节点放入队列中 标识置为true，重复上述过程：统计进队列或者出队列的次数就是当前岛屿的大小
    for(let i = 0; i < rol; i++){
        for(let j = 0; j < col; j++){
            //debugger
            let time = 0 //记录进队列的次数，就是当前陆地的面积
            //如果当前的节点是陆地且节点没有没访问过
            if(grid[i][j] === 1 && !TAG[i][j]){
                time++
                Queue.push([i,j])
                TAG[i][j] = true
                while(Queue.length){
                    //将它的四个方向的陆地添加进来
                    let [sr,sc] = Queue.shift()
                    if(sr>=1 && grid[sr - 1][sc] && !TAG[sr - 1][sc]){
                        //上方
                        time++
                        TAG[sr - 1][sc] = true
                        Queue.push([sr - 1,sc])
                    }
                    if(sr < (rol - 1) && grid[sr + 1][sc]  && !TAG[sr + 1][sc]){
                        //下方
                        time++
                        TAG[sr + 1][sc] = true
                        Queue.push([sr + 1,sc])
                    }
                    if(sc >= 1 && grid[sr][sc - 1] && !TAG[sr][sc - 1]){
                        //左边
                        time++
                        TAG[sr][sc - 1] = true
                        Queue.push([sr,sc - 1])
                    }
                    if(sc < (col - 1) && grid[sr][sc + 1] && !TAG[sr][sc + 1]){
                        //右边
                        time++
                        TAG[sr][sc + 1] = true
                        Queue.push([sr,sc + 1])
                    }
                }
                res = res > time ? res : time
            }
        }
    }
    return res

};
let grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]


let res = maxAreaOfIsland(grid)
console.log(res)
 */

/**
 * @param {number[][]} mat
 * @return {number[][]}
 */
 var updateMatrix = function(mat) {

    // f[m][n]标识当前点距离最近0的距离
    let rol = mat.length
    let col = mat[0].length
    let f = []
    for(let i = 0; i < rol; i++ ){
        f[i] = new Array(col).fill(Number.MAX_SAFE_INTEGER)
    }
    // 转移方程
    // f[m][n] = f[m][n] ? minDistancec(f[m -1][n],f[m + 1][n],f[m][n + 1],f[m][n - 1]) : 0
    // 这里遍历到m,n的时候它的左边节点和上面的f都已经求出来了，下面的还没有求出来
    //注意边界的处理
    // debugger
    let max = Number.MAX_SAFE_INTEGER
    for(let i = 0; i < rol; i++){
        for(let j = 0; j < col; j++){
            if(mat[i][j]){
                // 上面节点
                let top = i > 0 ? f[i - 1][j] : max
                let bottom = i < (rol - 1) ? (mat[i + 1][j] ? f[i + 1][j] : mat[i + 1][j]) : max
                let left = j > 0 ? f[i][j - 1] : max
                let right = j < (col - 1) ? (mat[i][j + 1] ? f[i][j + 1] : mat[i][j + 1]) : max
                f[i][j] = Math.min(top+1,bottom+1,left+1,right+1)
            }else{
                f[i][j] = mat[i][j]
            }
        }
    }
    return f
};
let arr = [[0,1,0,1,1],[1,1,0,0,1],[0,0,0,1,0],[1,0,1,1,1],[1,0,0,0,1]]
let res = updateMatrix(arr)
console.log(res)